The present invention relates to a behavioral synthesis method, a behavioral synthesis program and a behavioral synthesis apparatus, and in particular, a behavioral synthesis method, a behavioral synthesis program and a behavioral synthesis apparatus for behavioral-synthesizing a behavioral description describing operation behavior of variables.
In recent years, LSIs are becoming larger and larger in scale. As a result, it has been desired to develop more efficient design methods and design tools. Accordingly, for the functional designing of LSIs, a technique for behavioral-synthesizing a behavioral description, which is a description in a behavioral level, and thereby generating an RTL description, which is a description in a register-transfer level, has been known. In the behavioral synthesis, only the behavior is described by using a language resembling the C language without giving any consideration to circuit elements. Therefore, the circuit designing becomes easier and the design period can be reduced.
As a related-art behavioral synthesis method, “High-level synthesis” Yusuke Matsuyama, which is laid open in the Internet “<URL:http://www.c.csce.kyushu-u.ac.jp/˜matsunaga/lecture/lsic ad/pdf/Lecture06.pdf>”, discloses such a behavioral synthesis method. FIG. 28 shows a related-art behavioral synthesis method disclosed in the literature written by Yusuke Matsuyama.
As shown in FIG. 28, in the related-art behavioral synthesis method 900, a behavioral description describing the behavior of a circuit (901) is input to an HDL compiler. Then, the HDL compiler analyzes this behavioral description (902) and converts the behavioral description into an internal expression (903). As this internal expression, a control data flow graph (CDFG: Control Data Flow Graph) expressing a flow of data that appear in the behavioral description (data flow) and a flow of control for the execution order of each operation (control flow) is used.
For the generated internal expression, scheduling is performed (904). In the scheduling, specific control steps with which respective operations and/or data transfers in the behavioral description are executed are determined. Further, allocation is performed for the scheduled internal expression (905). In the allocation, a circuit configuration for achieving a desired behavior is determined.
When the scheduling and the allocation have been finished, a net list of a data paths (908) in which registers, functional units, multiplexers, and the like are used as circuit elements, and a control circuit table (907) indicating information about signals used to control behavior to be executed at each clock and state transitions for successive executions are generated (906).
FIGS. 29A, 29B and 29C show an example of an allocation process performed in the related-art behavioral synthesis method disclosed in the literature written by Yusuke Matsuyama.
In the related-art behavioral synthesis method, when a CDFG is generated based on a behavioral description and scheduling is performed, a post-scheduling CDFG like the one shown in FIG. 29A is generated. As a result, in the related-art behavioral synthesis method, registers are allocated to variables a, b, c, d and e, and adders are allocated to additions o1 and o2 by the allocation process.
In general, in the allocation process, “register sharing” in which a plurality of valuables are assigned to a common register is implemented in order to reduce the circuit size. FIGS. 29B and 29C are examples in which allocation is performed while sharing a register(s).
In the example shown in FIG. 29A, the variables a and b and an adder are simultaneously used and the variables d and c and another adder are simultaneously used. However, the other combinations are not simultaneously used. Therefore, in FIG. 29B, the variables a, d and e share a register r1, and registers r2 and r3 are allocated to the variables b and c respectively. Further, a multiplexer is allocated in order to select the value to be input to the shared adder.
Further, in FIG. 29C, the variables a and e share a register r1, and the variables b and d share a register r2. A register r3 is allocated to the variable c. Further, two multiplexers are allocated in order to select the shared register and the value to be input to the adder.
FIGS. 30A, 30B and 30C show an example of register sharing implemented in the related-art behavioral synthesis method disclosed in the literature written by Yusuke Matsuyama. Similarly to FIG. 29A, FIG. 30A shows a post-scheduling CDFG.
In the related-art behavioral synthesis method, when a post-scheduling CDFG is generated, the lifetime of each variable is calculated as shown in FIG. 30B. The lifetime is a period between when a value is written into a variable and when the value is used. That is, the lifetime is a period during which the value needs to be held in the variable.
In the example shown in FIG. 30B, the lifetime of the variable a starts at a time earlier than the step 1 and continues to the step 2. The lifetime of the variable b starts at a time earlier than the step 1 and continues to the step 1. The lifetime of the variable c starts at the step 1 and continues to the step 2. The lifetime of the variable d starts at the step 2 and continues to a time later than the step 2. Any variables whose lifetimes do not overlap each other can be assigned to the same register and thus that register can be shared.
In the related-art behavioral synthesis method, the variables a, b, c and d are sorted (arranged) according to the start times of their lifetimes as shown in FIG. 30C, and then the first variable is assigned to the first register. After that, variables are examined one by one and they are assigned to that register unless their lifetimes do not overlap each other. When no variable can be assigned to that register any more, a new register is prepared. Further, these processes are repeated until all the variables are assigned. In the example shown in FIG. 30C, firstly, since the lifetimes of the variables a and d do not overlap each other, a register r1 is allocated to and shared between them. Further, since the lifetimes of the variables b and c do not overlap each other, a register r2 is allocated to and shared between them.
Further, Japanese Patent No. 2861994 discloses a related-art behavioral synthesis method relating to the register sharing. FIGS. 31A and 31B show an example of register sharing in the related-art behavioral synthesis method disclosed in Japanese Patent No. 2861994.
FIGS. 31A and 31B show an example in which when variables a1 and b1 are to be transferred to registers c1 and c2 respectively, one register (five bits) is used as both the register c1 and the register c2. In FIG. 31A, when a 2-bit signed variable a1 and a 4-bit signed variable b1 are to be transferred to the common register (five bits), a number of bits by which the registers a1 and b1 are short in comparison to the destination register are added to the registers a1 and b1 respectively. Then, the variable to be transferred to the register is selected by a multiplexer (MUX). Note that since the 0th-bit of each of the variables a1 and b1 is a sign bit, the same data as the sign bit is inserted as the bit(s) to be added.
In FIG. 31B, when a 4-bit unsigned variable a2 and a 2-bit unsigned variable b2 are to be transferred to the common register (five bits), a number of bits by which the registers a2 and b2 are short in comparison to the destination register are added to the registers a2 and b2 respectively as in the case of the signed variables. Then, the variable to be transferred to the register is selected by the multiplexer (MUX). Note that since each of the variables a2 and b2 does not have the sign bit, data “0” is inserted as the as the bit(s) to be added.
Further, Japanese Unexamined Patent Application Publication No. 2011-34517 also discloses a technique related to the related-art behavioral synthesis method. However, Japanese Unexamined Patent Application Publication No. 2011-34517 discloses a technique relating to a verification method for verifying the result of behavioral synthesis, but does not disclose any specific behavioral synthesis method.